package 代码随想录_回溯.组合;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @create 2022-06-08 18:25
 */
public class 组合总和III_216 {
    /**
     * 回溯
     * 这个题为啥不去重了？？
     * 应该是集合原本就有序：[1,9]
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,n,1,0);
        return res;
    }
    private void dfs(int k, int n, int startIndex, int sum){
        if(sum > n) return;// 不要这行也能通过
        if(sum == n && list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = startIndex;i <= 9;i++){
            sum += i;
            list.add(i);
            dfs(k,n,i + 1,sum);
            //回溯
            //回溯过程是一一对应的,处理有加,回溯就要有减
            sum -= i;
            list.removeLast();
        }
    }
}
class combinationSum3way2{
    /**
     * 剪枝优化：参考77组合
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,n,1,0);
        return res;
    }
    private void dfs(int k,int n,int startIndex,int sum){
        //已选元素总和如果已经大于n,那么往后遍历就没有意义了
        if (sum > n) {//剪枝操作
            return;
        }
        if(list.size() == k){
            if(sum == n){
                res.add(new ArrayList<>(list));
            }
            //如果path.size() == k但sum != targetSum直接返回
            return;
        }
        for(int i = startIndex;i <= 9 - (k - list.size()) + 1;i++){//剪枝
            sum += i;
            list.add(i);
            dfs(k,n,i + 1,sum);
            //回溯
            //回溯过程是一一对应的,处理有加,回溯就要有减！
            sum -= i;
            list.removeLast();
        }
    }
}
